package com.tucc.hello.leetcode.no801_1200.no909;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] board = {
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 35, -1, -1, 13, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 15, -1, -1, -1, -1}};

        board = new int[][]{{-1, -1, -1}, {-1, 9, 8}, {-1, 8, 9}};

        board = new int[][]{{-1, 7, -1}, {-1, 6, 9}, {-1, -1, 2}};

        board = new int[][]{{-1, -1, 27, 13, -1, 25, -1}
                , {-1, -1, -1, -1, -1, -1, -1}
                , {44, -1, 8, -1, -1, 2, -1}
                , {-1, 30, -1, -1, -1, -1, -1}
                , {3, -1, 20, -1, 46, 6, -1}
                , {-1, -1, -1, -1, -1, -1, 29}
                , {-1, 29, 21, 33, -1, -1, -1}};
        System.out.println(solution.snakesAndLadders(board));
    }

    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        if (n <= 1) {
            return 0;
        }
        boolean flag = true;
        int num = 0;
        Map<Integer, Integer> snakes = new HashMap<>();

        for (int i = board.length - 1; i >= 0; i--) {
            int start = flag ? 0 : board[i].length - 1;
            int end = board.length - 1 - start;
            int step = flag ? 1 : -1;
            for (int j = start; flag ? j <= end : j >= end; j += step) {
                num++;
                if (board[i][j] != -1) {
                    snakes.put(num, board[i][j]);
                }
            }
            flag = !flag;
        }
        int step = 0;
        int end = n * n;
        boolean[] visit = new boolean[end + 1];
        List<Integer> startList = new ArrayList<>();
        startList.add(1);
        visit[1] = true;
        while (true) {
            if (startList.isEmpty()) {
                return -1;
            }
            step++;
            List<Integer> nextList = new ArrayList<>();
            for (int start : startList) {
                int max = start + 6;
                if (max >= end) {
                    return step;
                }
                for (int i = start + 1; i <= max; i++) {
                    if (visit[i]) {
                        continue;
                    }
                    visit[i] = true;
                    Integer snake = snakes.get(i);
                    if (snake != null) {
                        if (!visit[snake]) {
                            if (snake >= end) {
                                return step;
                            }
                            nextList.add(snake);
//                            visit[snake] = true;
                        }
                    } else {
                        nextList.add(i);
                    }
                }
            }
            startList = nextList;
        }
    }
}
